牛牛有两个长度为的数组,牛牛希望统计有多少数对满足:
1,
2,
对a数组统计前缀和,假设当前区间为[l,r],根据题意有pre[r + 1] - pre[l] == bl + br,变换等式为pre[r + 1] - br == bl + pre[l];因此我们倒序遍历b数组,枚举其左边界,同时统计pre[r + 1] - br的个数即可
import collections class Solution: def countLR(self , a , b ): # write code here pre = [0] for i in range(len(a)): pre.append(pre[-1] + a[i]) v = collections.defaultdict(int) ans = 0 for i in range(len(b) - 1,-1,-1): v[pre[i + 1] - b[i]] += 1 cur = b[i] + pre[i] ans += v[cur] return ans